Relative Convex Hull Determination from Convex Hulls in the Plane

摘要

A new algorithm for the determination of the relative convex hull in theplane of a simple polygon A with respect to another simple polygon B whichcontains A, is proposed. The relative convex hull is also known as geodesicconvex hull, and the problem of its determination in the plane is equivalent tofind the shortest curve among all Jordan curves lying in the difference set ofB and A and encircling A. Algorithms solving this problem known fromComputational Geometry are based on the triangulation or similar decompositionof that difference set. The algorithm presented here does not use suchdecomposition, but it supposes that A and B are given as ordered sequences ofvertices. The algorithm is based on convex hull calculations of A and B and ofsmaller polygons and polylines, it produces the output list of vertices of therelative convex hull from the sequence of vertices of the convex hull of A.